Scheduling involves the determination of a sequence of operations to satisfy a set of conditions and a set of goals concurrently. It is a process where limited resources, such as machines, material and tooling, are allocated over a period of time (“the scheduling horizon”) among both parallel and sequential activities. Frequently, a scheduling task must account for conflicting objectives, multiple constraints, different configurations of shop floors, various simultaneous orders, renewable and non-renewable resources and so on. In many cases, the combination of multiple goals and constraints results in an exponentially growing search space. Such problems are known as NP-hard problems (French 1982, Cleveland and Smith 1989), which cannot be solved by deterministic methods within polynomial time.
In a typical scheduling task, a set of work orders is scheduled across a set of work centers. As is known in the art, a work order (also referred to as a “job” or a “lot”) describes a set of operations that is to be performed to generate a product which may consist of a number of individual items. A work order typically includes a due date (i.e. a time by which completion of the work order is needed). A work center is a set of one or more machines on which a particular operation can be completed. A work center contains various machines having similar capabilities (e.g. in a semiconductor backend assembly environment, a “Wire Bond” work center may contain multiple wire bonders which come from different equipment manufacturers, yet they are all generally capable of completing the “wire bonding” operation). The relationship between work centers and operations can be one-to-one (e.g. as in the “Wire Bond” work centre for example) or one-to-many (e.g. in a typical precision machining job shop environment, a group of Computerized Numerical Control (CNC) machines may be considered as a “CNC Center” that is able to performing turning, milling, drilling, etc. operations.
Scheduling theory has received considerable attention from academic researchers, practitioners, management scientists, production and operation research workers and mathematicians since the early 1950s, such as those by Muth and Thompson (1963) and French (1982). Numerous approaches, such as operations research based techniques (Vairaktarakis and Elhafsi 2000, Hillier and Brandeau 2001, Mokotoff 2001), simulation-based and artificial intelligence (AI) based approaches (Murata et al. 1996, Kouiss et al. 1997, Khoo et al. 2001) have been suggested for solving scheduling problems or even the large-scale scheduling problems.
Due to the increasing competition and rising manufacturing costs, manufacturers must be more responsive to market conditions and customer requirements by employing new technologies, such as Finite Capacity Scheduling (FCS), in order to produce the desired quality and quantity of goods of the lowest cost at the right time. In recent years, FCS techniques have been adopted by a significant number of manufacturing firms.
Due to computational considerations, scheduling models are usually overly simplified. Within the scope of rigid simplifying assumptions, most scheduling models fail to provide practical implementable solutions for industry. Most of the mathematical models fail to incorporate decision-making based on the heuristics (i.e. the application of experience-derived knowledge to a problem). Some AI based methods are time-consuming in both phases of development and computation, and lack explanation capabilities, which are vital for the end user to understand the results. These models fail to account for the fact that a real manufacturing system is much more complex than a general job shop system, possibly having a stochastic environment, frequently varying virtual layout, dynamically changing states, multiple process plans, and other uncertainties. Often the static set of assumptions and input for those simplified models fail to consider such aspects of scheduling.
For these reasons, dispatching rules, such as shortest processing time, earliest due date, first in first out and least remaining slack time, have been applied to scheduling problems (Russell et al. 1987, Kutanoglu and Sabuncuoglu 1999). These procedures are designed to provide solutions to complex problems in real time.
Various performance measures pertaining to different factors, such as the time a job spends in the shop, performance relative to due date, utilization of production resources, and so on, have been identified to evaluate schedules. In most cases, the choice of a schedule is a trade-off among different performance measures. Some of the typical performance measures are:                Flow time: the amount of time a job spends from the moment it is ready until its completion;        Makespan: the amount of time for all jobs to complete processing;        Lateness: the amount of time a job is past its due date;        Earliness: the amount of time by which a job predates its due date;        Tardiness: equals lateness if the job is late, or zero if the job is early or on time;        Average Work in Progress (WIP) level: the mean value of the WIP. A higher WIP level means that more money is tied up in inventory; and        Machine utilization: the fraction of available time spent processing jobs versus being idle.        
Three scheduling procedures, namely, order-based scheduling, event-based scheduling (Taylor 2001) and resource-based scheduling (Plenert and Kirchmier 2000), are often employed.
In order-based scheduling (also known as “job-based scheduling”, “blocked-time approach” or “horizontal loading”), orders are scheduled through all work centers based on priority: the job with highest priority is scheduled through all work centers first, then the job with the second highest priority is scheduled through all work centers, and so on, until all jobs have been scheduled. If a lower priority job can be scheduled ahead of a higher priority job at a particular machine without delaying the scheduled start time of the higher priority job, this is permitted.
The order-based scheduling technique works well in environments in which the capacity utilization is low or some rush jobs need to be assigned in the shortest possible time. However, because order-based scheduling focuses on jobs rather than on machines, it can suffer from excess unused time blocks that could be used to schedule waiting lots. In other words, jobs are put into the schedule in sequence without regard for gaps in the machine schedule. Assuming the technique is applied alone without incorporation of any supplementary procedures, it may result in low machine utilization and lengthy average order throughput times.
Event-based scheduling (also called the “event-driven approach”, “simulation-based scheduling” or “vertical loading”) works in a manner similar to a discrete-event simulation of a shop floor or a factory, which is shown as operations 50 in FIG. 1. In this approach, each operation to be performed has an associated queue. One or more machines may be capable of completing each operation. At time zero, all the events are initialized and the simulation clock is advanced to the time that the next event occurs. Basically, three types of events are generated in the procedure:                New order released: in response to the event, the new order is added to the queue of the first operation in routing.        Order completed: the order is moved to the next operation queue in routing and the machine which completed processing of the operation is set to idle.        Machine idle: in response to this event, the highest priority order in the queue is selected and processing starts.        
The simulation clock is advanced and events are generated and processed until all the orders have been scheduled.
The event-based scheduling technique attempts to keep a machine busy if there is any job in the queue waiting for processing. This technique performs well in terms of the flow time and its variation, mean tardiness and makespan, and in environments in which high resource utilization is the main concern and all orders have similar priorities. However, if a pure event-based scheduling technique is applied, a higher priority order might be blocked by a lower priority order that arrives at the machine a short time earlier. Accordingly, this scheduling technique can only perform a local limited optimization instead of global optimization of the entire manufacturing system.
Resource-based scheduling is a technique that schedules bottleneck resources first to ensure that the utilization of these resources is maximized. The theory of constraints (TOC) is the basis of the technique. TOC can be described as a capacity-oriented system at the constraint and a material-oriented system at non-constraints. It generates schedules for the bottleneck resources over the entire scheduling horizon. All other schedules upstream and downstream from the bottleneck resources are then subordinated to this schedule. Although the conventional TOC approach attempts to maximize the throughput at a constraint by scheduling it first, scheduling of the upstream and downstream operations may not be performed.
What is needed is a scheduling approach which addresses at least some of the above-noted difficulties.